package com.example.javamaday.sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        Integer[] arr = {4, 5, 3, 9, 2, 1};
        sort(arr);
        System.out.println(Arrays.asList(arr).toString());
    }

    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        // 安全校验
        if (hi <= lo) {
            return;
        }
        // 需要对数组中lo索引到hi索引处的元素进行分组（分为：左子组和右子组）
        int partition = partition(a, lo, hi); // 返回的是分组的分界值所在的索引，即分界值变换后的索引
        // 让左子组有序
        sort(a, lo, partition - 1);
        // 让右子组有序
        sort(a, partition + 1, hi);

    }

    // 对数组a中，从索引lo到hi之间的元素进行分组，并返回分组界限所对应的索引
    private static int partition(Comparable[] a, int lo, int hi) {
        // 确定分界值
        Comparable key = a[lo];
        // 定义两个指针，分别指向待切分元素的最小索引处+1和最大索引处
        int left = lo;
        int right = hi + 1;
        while (true) {
            while (less(key, a[--right])) {
                if (right == lo) {
                    break;
                }
            }
            while (less(a[++left], key)) {
                if (left == hi) {
                    break;
                }
            }
            if (left >= right) {
                break;
            } else {
                exch(a, left, right);
            }
        }
        int cutoffIndex = right; // 也可以等于left（因为此时left和right是相等的）
        exch(a, lo, cutoffIndex);
        return cutoffIndex;
    }

    private static boolean less(Comparable i, Comparable j) {
        return i.compareTo(j) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
